/*
*	优先级队列(堆系列)
*/



//最后一块石头的重量
//https://leetcode.cn/problems/last-stone-weight/submissions/
class Solution {
public:
    int lastStoneWeight(vector<int>& stones) {
        priority_queue<int> pq(stones.begin(),stones.end());

        while(pq.size()>1)
        {
            int num1 = pq.top();
            pq.pop();
            int num2 = pq.top();
            pq.pop();
            if(num1-num2) pq.push(num1-num2);
        }
        if(pq.empty()) return 0;
        return pq.top();
    }
};



//数据流中的第k大元素
//https://leetcode.cn/problems/kth-largest-element-in-a-stream/submissions/
class KthLargest {
    //第k大 降序 建小堆
    priority_queue<int,vector<int>,greater<int>> pq;
    int k = 0;
public:
    KthLargest(int k, vector<int>& nums) {
        this->k = k;
        for(auto& n:nums)
        {
            pq.push(n);
            while(pq.size()>k) pq.pop();
        }
    }
    
    int add(int val) {
        pq.push(val);
        while(pq.size()>k) pq.pop();
        return pq.top();
    }
};



//前k个高频单词
//https://leetcode.cn/problems/top-k-frequent-words/submissions/
class Solution {
    using PSI = pair<string,int>;
    struct comp
    {
        bool operator()(const PSI& left,const PSI& right)
        {
            //如果出现次数相等 则比较ASCII 谁小谁在前面
            if(left.second == right.second) return left.first<right.first;
            return left.second > right.second; //谁出现次数多谁就在前面
        }
    };
public:
    vector<string> topKFrequent(vector<string>& words, int k) {
        unordered_map<string,int> hash;
        for(const auto& s:words) ++hash[s];

        priority_queue<PSI,deque<PSI>,comp> pq;

        for(auto& x:hash)
        {
            pq.push(x);
            while(pq.size()>k) pq.pop();
        }
        vector<string> ret(k);
        for(int i = k-1;i>=0;--i)
        {
            ret[i] = pq.top().first;
            pq.pop();
        }
        return ret;
    }
};



//数据流的中位数
//https://leetcode.cn/problems/find-median-from-data-stream/submissions/
class MedianFinder {
public:
    //因为是找中位数
    //我们可以把数组分为两段 左边一段右边一段 如果两边元素数相等则 两边的最后一个和第一个就是中位数
    //否则 左边的最后一个就是中位数
    //既然这样 可以将这两段数 分为两个堆 左边是大堆 右边是小堆
    //这样左边堆顶取的就是左边部分最后一个数 右边部分取的就是右边第一个数
    //因为中位数要求数据有序所以这样数据就有序且能快速查找
    MedianFinder() {

    }

    void addNum(int num) {
        if (left.size() == 0 || num < left.top()) left.push(num);
        else right.push(num);

        while (left.size() < right.size())
        {
            left.push(right.top());
            right.pop();
        }

        while (left.size() > right.size() + 1)
        {
            right.push(left.top());
            left.pop();
        }
        
    }

    double findMedian() {
        if (left.size() == right.size()) return (left.top() + right.top()) / 2.0;
        return left.top();
    }
private:
    priority_queue<int> left;  //大堆
    priority_queue<int, deque<int>, greater<int>> right; //小堆

};



